/*
 * simple linked list: SList
 */
#ifndef __SLIST_H__
#define __SLIST_H__

#include <iostream>

using namespace std;

#undef NULL
#define NULL 0

template <typename T>
class Node {
    public:
        Node(const T& data): _next(NULL), _prev(NULL), _key(data) {}
        ~Node() {_next = _prev  = NULL;}
        const T& key() {return _key;}
        Node<T> *_next;
        Node<T> *_prev;

    private:
        T _key;
};

template <typename T>
class SList {
    public:
        SList(): _head(NULL), _nelems(0) {}
        SList(Node<T> *n): _head(n) {_nelems = 1;}
        ~SList() {_head = NULL;}
        bool append(const T& data);     // append a node with key == data
        Node<T> *find(const T& data);   // find a node with key == data
        bool remove(Node<T> *n);        // remove a node n from the list
        bool remove(const T& data);     // remove a node with key == data
        void reverse();                 // reverse the entire linked list
        void reverse(int n, int m);     // reverse the linked list between
                                        // elem n and elem m (m > n)
        void printlist();

    private:
        Node<T> *_head;
        int _nelems;
        Node<T> *_create_node(const T& data);
        void _delete_node(Node<T> *n);
};

template <typename T>
bool SList<T>::append(const T&data)
{
    Node<T> *n = _create_node(data);
    if (!n) return false;
    if (_head) {
        _head->_prev = n;
        n->_next = _head;
    }
    _head = n;
    _nelems ++;
    return true;
}

template <typename T>
Node<T> *SList<T>::find(const T&data)
{
    Node<T> *n;
    for (n = _head; n != NULL; n = n->_next) {
        //TODO user-supplied compare func
        if (data == n->key())
            break;
    }
    return n;
}

template <typename T>
bool SList<T>::remove(Node<T> *n)
{
    if (n == NULL) return false;
    if (n->_next)
        n->_next->_prev = n->_prev;
    if (n->_prev)
        n->_prev->_next = n->_next;
    else  // first elem in the list
        _head = n->_next;
    _delete_node(n);
    _nelems--;
    return true;
}

template <typename T>
void SList<T>::reverse()
{
    if (_nelems)
        return reverse(1, _nelems);
}

template <typename T>
void SList<T>::reverse(int n, int m)
{
    Node<T> *p_start, *p_start_prev;
    Node<T> *p, *p_next;

    // no action if reverse the same elem
    if (n < 1) n = 1; 
    if (m > _nelems) m = _nelems;
    if (n == m) return;

    p = _head;
    for (int i = 1; i < n; i++)
        p = p->_next;
    p_start = p;
    p_start_prev = p->_prev;
    p_next = (p)?(p->_next):NULL;

    // reverse the items from n to m
    for (int j = 1; j <= m-n; j++) {
        Node<T> *p_next_next = (p_next)?(p_next->_next):NULL;
        // reverse p and p_next
        p->_prev = p_next;
        p_next->_next = p;
        // advance pointers
        p = p_next;
        p_next = p_next_next;
    }

    // adjust (n-1) and (m+1)
    p->_prev = p_start_prev;
    if (p_start_prev)
        p_start_prev->_next = p;
    else  // first item
        _head = p;
    p_start->_next = p_next;
    if (p_next)
        p_next->_prev = p_start;

    return;
}

template <typename T>
bool SList<T>::remove(const T&data)
{
    Node<T> *n = find(data);
    return remove(n);
}

template <typename T>
Node<T> *SList<T>::_create_node(const T&data)
{
    Node<T> *n = new Node<T>(data);
    return n;
}

template <typename T>
void SList<T>::_delete_node(Node<T> *n)
{
    delete n;
}

template <typename T>
void SList<T>::printlist()
{
    int i = 1;
    Node<T> *n;
    if (NULL == _head) {
        cout << "empty list" << endl;
        return;
    }
    for (n = _head; n != NULL; i++, n = n->_next) {
        if (i > 1) cout << " --> ";
        cout << n->key();
        if (i % 10 == 0) cout << endl;
    }
    cout << endl;
}
#endif
